#include <cstdlib>
#include <ctime>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define MAX_N 10000000
#define ROOT 1
#define FATHER(i) ((i) / 2)
#define LEFT(i)   ((i) * 2)
#define RIGHT(i)  ((i) * 2 + 1)
#define cmp >
#define swap(a, b){\
    __typeof(a)__c = (a);\
    (a) = (b);(b) = __c;\
    }


#define TEST(func, arr, n){\
    printf("TEST: %s ", #func);\
    int *tmp = (int *)malloc(sizeof(int) * n);\
    memcpy(tmp, arr, sizeof(int) * n);\
    long long begin = clock();\
    func(tmp, n);\
    long long end = clock();\
    if(check(tmp, n)){\
        printf("OK\t");\
    }else{\
        printf("FAIL\t");\
    }\
    printf("%lld ms\n", 1000 *(end - begin) / CLOCKS_PER_SEC);\
    free(tmp);\
}

bool check(int *arr, int n){
    for(int i = 1; i < n; i++){
        if(arr[i] < arr[i - 1]) return false;
    }
    return true;
}

int *getRandData(int n){
    int *arr = (int *)malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++) arr[i] = rand() % 100000;
    return arr;
}

inline void up_update(int *data, int i){
    while(i > ROOT && data[i] cmp data[FATHER(i)]){
        swap(data[i], data[FATHER(i)]);
        i = FATHER(i);
    }
    return;
}

inline void down_update(int *data, int i, int n){
    while(LEFT(i) <= n){
        int idx = i, l = LEFT(i), r = RIGHT(i);
        if(data[l] cmp data[idx]) idx = l;
        if(r <= n && data[r] cmp data[idx]) idx = r;
        if(idx == i) break;
        swap(data[i], data[idx]);
        i = idx;
    }
    return;
}

void normal_heap_build(int *data, int n){
    for(int i = 2; i<= n; i++){
        up_update(data, i);
    }
    return;
}

void linear_heap_build(int *data, int n){
    for(int i = n / 2; i>= 1; i--){
        down_update(data, i, n);
    }
    return;
}

void heap_sort_final(int *data, int n){
    for(int i = n; i>= 2; i--){
        swap(data[ROOT], data[i]);
        down_update(data, ROOT, i-1);
    }
    return;
}

void normal_heap(int *arr, int n){
    int *data = arr - 1;
    normal_heap_build(data, n);
    heap_sort_final(data, n);
    return;
}

void linear_heap(int *arr, int n){
    int *data = arr - 1;
    linear_heap_build(data, n);
    heap_sort_final(data, n);
    return;
}

int main(){
    srand(time(0));
    int *arr = getRandData(MAX_N);
    TEST(normal_heap, arr, MAX_N);
    TEST(linear_heap, arr, MAX_N);
    return 0;
}